package weekMatch.one_343;

import java.util.*;

public class LeeCode_03 {
    public static void main(String[] args) {
//        System.out.println(minimumCost(new int[]{1, 1}, new int[]{4, 5},
//                new int[][]{{1, 2, 3, 3, 2}, {3, 4, 4, 5, 1}}));
//        System.out.println(minimumCost(new int[]{1, 1}, new int[]{5, 10},
//                new int[][]{{3,4,5,2,5}, {4,5,3,8,3},{3,2,5,3,1}}));
        System.out.println(minimumCost(new int[]{1, 1}, new int[]{7, 9},
                new int[][]{{1,5,6,9,5}, {1,6,4,7,5},{6,2,6,9,4}}));
    }

    private static int minimumCost(int[] start, int[] target, int[][] specialRoads) {
        Map<String, Integer> map = new HashMap<>();
        Set<String> used = new HashSet<>();
        String stKey = start[0] + "," + start[1];
        map.put(stKey, 0);
        String endKey = target[0] + "," + target[1];
        map.put(endKey, Math.abs(target[0] - start[0]) + Math.abs(target[1] - start[1]));
        for (int[] specialRoad : specialRoads) {
            int l1 = Math.abs(specialRoad[0] - start[0]) + Math.abs(specialRoad[1] - start[1]) + specialRoad[4];
            int l2 = Math.abs(specialRoad[2] - start[0]) + Math.abs(specialRoad[3] - start[1]);
            String key = specialRoad[2] + "," + specialRoad[3];
            if (map.containsKey(key)){
                map.put(key, Math.min(map.get(key), Math.min(l1, l2)));
            }else {
                map.put(key, Math.min(l1, l2));
            }
        }
        used.add(stKey);
        while (!used.contains(endKey)) {
            Set<String> set = map.keySet();
            int minDis = Integer.MAX_VALUE;
            String minKey = "";
            for (String key : set) {
                if (!used.contains(key) && map.get(key) < minDis) {
                    minDis = map.get(key);
                    minKey = key;
                }
            }
            used.add(minKey);
            String[] tmp = minKey.split(",");
            int[] point = new int[]{Integer.parseInt(tmp[0]), Integer.parseInt(tmp[1])};
            for (int[] specialRoad : specialRoads) {
                String key = specialRoad[2] + "," + specialRoad[3];
                if (used.contains(key)){
                    continue;
                }
                int l1 = Math.abs(point[0] - specialRoad[2]) + Math.abs(point[1] - specialRoad[3]);
                int l2 = Math.abs(point[0] - specialRoad[0]) + Math.abs(point[1] - specialRoad[1]) + specialRoad[4];
                map.put(key, Math.min(map.get(key), Math.min(l1, l2) + map.get(minKey)));
            }
            map.put(endKey, Math.min(map.get(endKey), map.get(minKey) + Math.abs(point[0] - target[0]) + Math.abs(point[1] - target[1])));
        }
        return map.get(endKey);
    }
}
